package com.neusoft.recursion.eightQueen;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 八皇后问题
 * @date 2023-01-09
 */
public class EightQueens {

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();

        long start = System.currentTimeMillis();
        List<int[]> result = eightQueens.eightQueens();
        long end = System.currentTimeMillis();

        System.out.println("耗时" + (end - start) + "ms");

        System.out.println("一共有" + result.size() + "种解法");

        for (int[] solution : result) {
            printQueen(solution);
            System.out.println("===================");
        }
    }

    /**
     * 暴力穷举法: O(n^n)
     *
     * @return 八皇后的成功解法集合
     */
    public List<int[]> exhaustion() {
        // 保存结果
        ArrayList<int[]> result = new ArrayList<>();
        // 皇后的数量: 八皇后
        int queenSize = 8;
        // 用一个数组保存当前考察的一组解
        int[] solution = new int[queenSize];
        // 遍历所有可能的情况
        for (solution[0] = 0; solution[0] < queenSize; solution[0]++) {
            for (solution[1] = 0; solution[1] < queenSize; solution[1]++) {
                for (solution[2] = 0; solution[2] < queenSize; solution[2]++) {
                    for (solution[3] = 0; solution[3] < queenSize; solution[3]++) {
                        for (solution[4] = 0; solution[4] < queenSize; solution[4]++) {
                            for (solution[5] = 0; solution[5] < queenSize; solution[5]++) {
                                for (solution[6] = 0; solution[6] < queenSize; solution[6]++) {
                                    for (solution[7] = 0; solution[7] < queenSize; solution[7]++) {
                                        // 判断如果符合要求，直接保存到result
                                        if (check(solution)) {
                                            result.add(Arrays.copyOf(solution, queenSize));
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    /**
     * 回溯法
     *
     * @return 八皇后的成功解法集合
     */
    public List<int[]> eightQueens() {
        // 保存结果
        ArrayList<int[]> result = new ArrayList<>();

        // 用一个数组保存当前考察的一组解
        int[] solution = new int[8];

        Arrays.fill(solution, -1);

        // 单独调用一个递归方法进行回溯
        backtrack(result, solution, 0);

        return result;
    }

    /**
     * 定义HashSet保存出现过的col、diag1、diag2
     */
    HashSet<Integer> cols = new HashSet<>();
    HashSet<Integer> diags1 = new HashSet<>();
    HashSet<Integer> diags2 = new HashSet<>();

    /**
     * 递归方法
     *
     * @param result   八皇后的成功解法集合
     * @param solution 当前的的一组解
     * @param row      第一行index
     */
    private void backtrack(ArrayList<int[]> result, int[] solution, int row) {
        // 结束条件，全部行皇后位置都找到
        if (row >= 8) {
            result.add(Arrays.copyOf(solution, 8));
        } else {
            // 对当前行，判断每一个位置是否可行
            for (int col = 0; col < 8; col++) {
                // 1、 判断当前皇后位置是否有冲突
                int diag1 = row - col;
                int diag2 = row + col;

                if (cols.contains(col) || diags1.contains(diag1) || diags2.contains(diag2)) {
                    continue;
                }

                // 2、 保存当前皇后位置
                solution[row] = col;
                cols.add(col);
                diags1.add(diag1);
                diags2.add(diag2);

                // 3、 递归调用，处理下一行
                backtrack(result, solution, row + 1);

                // 4、 回溯
                solution[row] = -1;
                cols.remove(col);
                diags1.remove(diag1);
                diags2.remove(diag2);
            }
        }
    }

    /**
     * 打印八皇后解法
     *
     * @param solution 当前的一组解
     */
    public static void printQueen(int[] solution) {
        // 八皇后解法数量
        int n = solution.length;
        for (int solutionIndex : solution) {
            String[] line = new String[n];
            Arrays.fill(line, "□");
            line[solutionIndex] = "Q";
            // 把当前行打印输出
            for (String tempSymbol : line) {
                System.out.print(tempSymbol + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 检查当前解是否可行
     *
     * @param a 当前8皇后解法
     * @return 解法是否满足要求
     */
    private boolean check(int[] a) {
        // 判断任意两行皇后是否冲突: 是否同一行(已规避，已经默认分了8行)、同一列、同一斜线
        for (int i = 0; i < 7; i++) {
            for (int j = i + 1; j < 8; j++) {
                if (a[i] == a[j] || Math.abs(a[i] - a[j]) == j - i) {
                    return false;
                }
            }
        }
        return true;
    }
}
